package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/find-largest-value-in-each-tree-row/'>在每个树行中找最大值(Find Largest Value in Each Tree Row)</a>
 * <p>给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例1：
 *      输入: root = [1,3,2,5,3,null,9]
 *                  1
 *                /  \
 *               3    2
 *              / \    \
 *             5   3    9
 *      输出: [1,3,9]
 *
 * 示例2：
 *      输入: root = [1,2,3]
 *                  1
 *                /  \
 *               2    3
 *      输出: [1,3]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>二叉树的节点个数的范围是 [0,10^4]</li>
 *     <li>-2^31 <= Node.val <= 2^31 - 1</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/8 14:05
 */
public class LC0515FindLargestValueInEachTreeRow_M {
    static class Solution {
        public List<Integer> largestValues(TreeNode root) {
            //return largestValuesByIterator(root);
            return largestValuesByRecursion(root);
        }

        private List<Integer> largestValuesByIterator(TreeNode root) {
            List<Integer> resList = new ArrayList<>();
            if (root == null) {
                return resList;
            }
            Queue<TreeNode> helper = new LinkedList<>();
            helper.offer(root);
            while (!helper.isEmpty()) {
                int currLevelNodeSize = helper.size();
                int currLevelMaxVal = Integer.MIN_VALUE;
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = helper.poll();
                    if (currNode != null) {
                        currLevelMaxVal = Math.max(currLevelMaxVal, currNode.val);
                        if (currNode.left != null) {
                            helper.offer(currNode.left);
                        }
                        if (currNode.right != null) {
                            helper.offer(currNode.right);
                        }
                    }
                }
                resList.add(currLevelMaxVal);
            }
            return resList;
        }

        private List<Integer> largestValuesByRecursion(TreeNode root) {
            List<Integer> resList = new ArrayList<>();
            largestValuesByRecursion(root, resList, 0);
            return resList;
        }

        private void largestValuesByRecursion(TreeNode root, List<Integer> resList, int level) {
            if (root == null) {
                return;
            }
            // 出现新的一层
            if (resList.size() == level) {
                resList.add(root.val);
            } else {
                resList.set(level, Math.max(resList.get(level), root.val));
            }
            largestValuesByRecursion(root.left, resList, level + 1);
            largestValuesByRecursion(root.right, resList, level + 1);
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(3);
        root1.right = new TreeNode(2);
        root1.left.left = new TreeNode(5);
        root1.left.right = new TreeNode(3);
        root1.right.right = new TreeNode(9);

        TreeNode root2 = new TreeNode(1);
        root2.left  = new TreeNode(2);
        root2.right  = new TreeNode(3);

        Solution solution = new Solution();
        Printer.printListInteger(solution.largestValues(root1));
        Printer.printListInteger(solution.largestValues(root2));
    }
}
